(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(1) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = x1   
POL(U13(x1)) = 2·x1   
POL(U21(x1)) = 2·x1   
POL(U22(x1)) = x1   
POL(U23(x1)) = x1   
POL(U24(x1)) = 2·x1   
POL(U25(x1)) = 2·x1   
POL(U26(x1)) = 2·x1   
POL(U31(x1)) = 2·x1   
POL(U32(x1)) = x1   
POL(U33(x1)) = 2·x1   
POL(U41(x1)) = 2·x1   
POL(U42(x1)) = x1   
POL(U43(x1)) = x1   
POL(U44(x1)) = 2·x1   
POL(U45(x1)) = 2·x1   
POL(U46(x1)) = 2·x1   
POL(U51(x1)) = 2·x1   
POL(U52(x1)) = x1   
POL(U53(x1)) = x1   
POL(U54(x1)) = x1   
POL(U55(x1)) = 2·x1   
POL(U56(x1)) = x1   
POL(U61(x1)) = x1   
POL(U62(x1)) = 2·x1   
POL(U63(x1)) = x1   
POL(U71(x1)) = 2·x1   
POL(U72(x1)) = 2·x1   
POL(U73(x1)) = 2·x1   
POL(U74(x1)) = 2·x1   
POL(U81(x1)) = 2·x1   
POL(U82(x1)) = 2·x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = x1   
POL(U92(x1)) = x1   
POL(__(x1, x2)) = 1 + 2·x1 + x2   
POL(isList) = 0   
POL(isNeList) = 0   
POL(isNePal) = 0   
POL(isPal) = 0   
POL(isPalListKind) = 0   
POL(isQid) = 0   
POL(nil) = 2   
POL(tt) = 0   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X


(2) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(3) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = 2·x1   
POL(U13(x1)) = 2·x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = 2·x1   
POL(U23(x1)) = x1   
POL(U24(x1)) = x1   
POL(U25(x1)) = x1   
POL(U26(x1)) = x1   
POL(U31(x1)) = 2·x1   
POL(U32(x1)) = 2·x1   
POL(U33(x1)) = x1   
POL(U41(x1)) = x1   
POL(U42(x1)) = 2·x1   
POL(U43(x1)) = 2·x1   
POL(U44(x1)) = x1   
POL(U45(x1)) = x1   
POL(U46(x1)) = 2·x1   
POL(U51(x1)) = 2·x1   
POL(U52(x1)) = x1   
POL(U53(x1)) = 2·x1   
POL(U54(x1)) = 2·x1   
POL(U55(x1)) = 2·x1   
POL(U56(x1)) = 2·x1   
POL(U61(x1)) = x1   
POL(U62(x1)) = x1   
POL(U63(x1)) = x1   
POL(U71(x1)) = 1 + 2·x1   
POL(U72(x1)) = 1 + x1   
POL(U73(x1)) = x1   
POL(U74(x1)) = 2·x1   
POL(U81(x1)) = 1 + x1   
POL(U82(x1)) = 1 + 2·x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = 2·x1   
POL(U92(x1)) = x1   
POL(isList) = 0   
POL(isNeList) = 0   
POL(isNePal) = 1   
POL(isPal) = 1   
POL(isPalListKind) = 0   
POL(isQid) = 0   
POL(tt) = 0   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

isNePalU61(isPalListKind)
isPaltt


(4) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(5) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = x1   
POL(U13(x1)) = 2·x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = 2·x1   
POL(U23(x1)) = 2·x1   
POL(U24(x1)) = 2·x1   
POL(U25(x1)) = 2·x1   
POL(U26(x1)) = x1   
POL(U31(x1)) = x1   
POL(U32(x1)) = 2·x1   
POL(U33(x1)) = 2·x1   
POL(U41(x1)) = x1   
POL(U42(x1)) = x1   
POL(U43(x1)) = 2·x1   
POL(U44(x1)) = 2·x1   
POL(U45(x1)) = 2·x1   
POL(U46(x1)) = x1   
POL(U51(x1)) = 2·x1   
POL(U52(x1)) = 2·x1   
POL(U53(x1)) = x1   
POL(U54(x1)) = 2·x1   
POL(U55(x1)) = x1   
POL(U56(x1)) = 2·x1   
POL(U61(x1)) = 2 + 2·x1   
POL(U62(x1)) = 2 + 2·x1   
POL(U63(x1)) = 1 + x1   
POL(U71(x1)) = 2·x1   
POL(U72(x1)) = 2·x1   
POL(U73(x1)) = 2·x1   
POL(U74(x1)) = 2·x1   
POL(U81(x1)) = 2·x1   
POL(U82(x1)) = 2·x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = x1   
POL(U92(x1)) = 2·x1   
POL(isList) = 0   
POL(isNeList) = 0   
POL(isNePal) = 0   
POL(isPal) = 0   
POL(isPalListKind) = 0   
POL(isQid) = 0   
POL(tt) = 0   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

U62(tt) → U63(isQid)
U63(tt) → tt


(6) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(7) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = x1   
POL(U13(x1)) = 2·x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = x1   
POL(U23(x1)) = 2·x1   
POL(U24(x1)) = 2·x1   
POL(U25(x1)) = 2·x1   
POL(U26(x1)) = x1   
POL(U31(x1)) = x1   
POL(U32(x1)) = 2·x1   
POL(U33(x1)) = 2·x1   
POL(U41(x1)) = x1   
POL(U42(x1)) = 2·x1   
POL(U43(x1)) = x1   
POL(U44(x1)) = 2·x1   
POL(U45(x1)) = 2·x1   
POL(U46(x1)) = 2·x1   
POL(U51(x1)) = 2·x1   
POL(U52(x1)) = x1   
POL(U53(x1)) = x1   
POL(U54(x1)) = 2·x1   
POL(U55(x1)) = x1   
POL(U56(x1)) = 2·x1   
POL(U61(x1)) = 1 + 2·x1   
POL(U62(x1)) = x1   
POL(U71(x1)) = 2·x1   
POL(U72(x1)) = 2·x1   
POL(U73(x1)) = 2·x1   
POL(U74(x1)) = 2·x1   
POL(U81(x1)) = 2·x1   
POL(U82(x1)) = 2·x1   
POL(U83(x1)) = 2·x1   
POL(U91(x1)) = x1   
POL(U92(x1)) = x1   
POL(isList) = 0   
POL(isNeList) = 0   
POL(isNePal) = 0   
POL(isPal) = 0   
POL(isPalListKind) = 0   
POL(isQid) = 0   
POL(tt) = 0   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

U61(tt) → U62(isPalListKind)


(8) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(9) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(10) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U111(tt) → U121(isPalListKind)
U111(tt) → ISPALLISTKIND
U121(tt) → U131(isNeList)
U121(tt) → ISNELIST
U211(tt) → U221(isPalListKind)
U211(tt) → ISPALLISTKIND
U221(tt) → U231(isPalListKind)
U221(tt) → ISPALLISTKIND
U231(tt) → U241(isPalListKind)
U231(tt) → ISPALLISTKIND
U241(tt) → U251(isList)
U241(tt) → ISLIST
U251(tt) → U261(isList)
U251(tt) → ISLIST
U311(tt) → U321(isPalListKind)
U311(tt) → ISPALLISTKIND
U321(tt) → U331(isQid)
U321(tt) → ISQID
U411(tt) → U421(isPalListKind)
U411(tt) → ISPALLISTKIND
U421(tt) → U431(isPalListKind)
U421(tt) → ISPALLISTKIND
U431(tt) → U441(isPalListKind)
U431(tt) → ISPALLISTKIND
U441(tt) → U451(isList)
U441(tt) → ISLIST
U451(tt) → U461(isNeList)
U451(tt) → ISNELIST
U511(tt) → U521(isPalListKind)
U511(tt) → ISPALLISTKIND
U521(tt) → U531(isPalListKind)
U521(tt) → ISPALLISTKIND
U531(tt) → U541(isPalListKind)
U531(tt) → ISPALLISTKIND
U541(tt) → U551(isNeList)
U541(tt) → ISNELIST
U551(tt) → U561(isList)
U551(tt) → ISLIST
U711(tt) → U721(isPalListKind)
U711(tt) → ISPALLISTKIND
U721(tt) → U731(isPal)
U721(tt) → ISPAL
U731(tt) → U741(isPalListKind)
U731(tt) → ISPALLISTKIND
U811(tt) → U821(isPalListKind)
U811(tt) → ISPALLISTKIND
U821(tt) → U831(isNePal)
U821(tt) → ISNEPAL
U911(tt) → U921(isPalListKind)
U911(tt) → ISPALLISTKIND
ISLISTU111(isPalListKind)
ISLISTISPALLISTKIND
ISLISTU211(isPalListKind)
ISNELISTU311(isPalListKind)
ISNELISTISPALLISTKIND
ISNELISTU411(isPalListKind)
ISNELISTU511(isPalListKind)
ISNEPALU711(isQid)
ISNEPALISQID
ISPALU811(isPalListKind)
ISPALISPALLISTKIND
ISPALLISTKINDU911(isPalListKind)
ISPALLISTKINDISPALLISTKIND

The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(11) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 30 less nodes.

(12) Complex Obligation (AND)

(13) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKINDU911(isPalListKind)
ISPALLISTKINDISPALLISTKIND

The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(14) UsableRulesProof (EQUIVALENT transformation)

We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.

(15) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKINDU911(isPalListKind)
ISPALLISTKINDISPALLISTKIND

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(16) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISPALLISTKINDU911(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISPALLISTKINDU911(tt)
ISPALLISTKINDU911(U91(isPalListKind))

(17) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKINDISPALLISTKIND
ISPALLISTKINDU911(tt)
ISPALLISTKINDU911(U91(isPalListKind))

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(18) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = ISPALLISTKIND evaluates to t =ISPALLISTKIND

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
  • Matcher: [ ]
  • Semiunifier: [ ]




Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from ISPALLISTKIND to ISPALLISTKIND.



(19) NO

(20) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPALU811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
ISNEPALU711(isQid)
U711(tt) → U721(isPalListKind)

The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(21) UsableRulesProof (EQUIVALENT transformation)

We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.

(22) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPALU811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
ISNEPALU711(isQid)
U711(tt) → U721(isPalListKind)

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(23) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNEPALU711(isQid) at position [0] we obtained the following new rules [LPAR04]:

ISNEPALU711(tt)

(24) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPALU811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPALU711(tt)

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(25) UsableRulesProof (EQUIVALENT transformation)

We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.

(26) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPALU811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPALU711(tt)

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(27) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISPALU811(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISPALU811(tt)
ISPALU811(U91(isPalListKind))

(28) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPALU711(tt)
ISPALU811(tt)
ISPALU811(U91(isPalListKind))

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(29) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U811(tt) → U821(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U811(tt) → U821(tt)
U811(tt) → U821(U91(isPalListKind))

(30) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPALU711(tt)
ISPALU811(tt)
ISPALU811(U91(isPalListKind))
U811(tt) → U821(tt)
U811(tt) → U821(U91(isPalListKind))

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(31) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U711(tt) → U721(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U711(tt) → U721(tt)
U711(tt) → U721(U91(isPalListKind))

(32) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U821(tt) → ISNEPAL
ISNEPALU711(tt)
ISPALU811(tt)
ISPALU811(U91(isPalListKind))
U811(tt) → U821(tt)
U811(tt) → U821(U91(isPalListKind))
U711(tt) → U721(tt)
U711(tt) → U721(U91(isPalListKind))

The TRS R consists of the following rules:

isPalListKindtt
isPalListKindU91(isPalListKind)
U91(tt) → U92(isPalListKind)
U92(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(33) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

s = ISPAL evaluates to t =ISPAL

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
  • Matcher: [ ]
  • Semiunifier: [ ]




Rewriting sequence

ISPALU811(tt)
with rule ISPALU811(tt) at position [] and matcher [ ]

U811(tt)U821(tt)
with rule U811(tt) → U821(tt) at position [] and matcher [ ]

U821(tt)ISNEPAL
with rule U821(tt) → ISNEPAL at position [] and matcher [ ]

ISNEPALU711(tt)
with rule ISNEPALU711(tt) at position [] and matcher [ ]

U711(tt)U721(tt)
with rule U711(tt) → U721(tt) at position [] and matcher [ ]

U721(tt)ISPAL
with rule U721(tt) → ISPAL

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.



(34) NO

(35) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
ISNELISTU411(isPalListKind)
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST

The TRS R consists of the following rules:

U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(36) UsableRulesProof (EQUIVALENT transformation)

We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.

(37) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
ISNELISTU411(isPalListKind)
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(38) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNELISTU411(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))

(39) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(40) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U411(tt) → U421(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))

(41) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(42) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U421(tt) → U431(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))

(43) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(44) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U431(tt) → U441(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))

(45) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(46) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U441(tt) → U451(isList) at position [0] we obtained the following new rules [LPAR04]:

U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))

(47) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(48) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNELISTU511(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))

(49) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(50) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U511(tt) → U521(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))

(51) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(52) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U521(tt) → U531(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))

(53) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(54) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U531(tt) → U541(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))

(55) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(56) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U541(tt) → U551(isNeList) at position [0] we obtained the following new rules [LPAR04]:

U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))

(57) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(58) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISLISTU111(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))

(59) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U111(tt) → U121(isPalListKind)
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(60) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U111(tt) → U121(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))

(61) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
ISLISTU211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(62) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISLISTU211(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))

(63) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(64) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U211(tt) → U221(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))

(65) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(66) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U221(tt) → U231(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))

(67) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(68) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U231(tt) → U241(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U231(tt) → U241(tt)
U231(tt) → U241(U91(isPalListKind))

(69) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))
U231(tt) → U241(tt)
U231(tt) → U241(U91(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(70) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U241(tt) → U251(isList) at position [0] we obtained the following new rules [LPAR04]:

U241(tt) → U251(U11(isPalListKind))
U241(tt) → U251(tt)
U241(tt) → U251(U21(isPalListKind))

(71) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELISTU411(tt)
ISNELISTU411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELISTU511(tt)
ISNELISTU511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLISTU111(tt)
ISLISTU111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLISTU211(tt)
ISLISTU211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))
U231(tt) → U241(tt)
U231(tt) → U241(U91(isPalListKind))
U241(tt) → U251(U11(isPalListKind))
U241(tt) → U251(tt)
U241(tt) → U251(U21(isPalListKind))

The TRS R consists of the following rules:

isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isPalListKindtt
isPalListKindU91(isPalListKind)
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
U13(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
isQidtt
U33(tt) → tt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(72) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

s = ISLIST evaluates to t =ISLIST

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
  • Matcher: [ ]
  • Semiunifier: [ ]




Rewriting sequence

ISLISTU211(tt)
with rule ISLISTU211(tt) at position [] and matcher [ ]

U211(tt)U221(tt)
with rule U211(tt) → U221(tt) at position [] and matcher [ ]

U221(tt)U231(tt)
with rule U221(tt) → U231(tt) at position [] and matcher [ ]

U231(tt)U241(tt)
with rule U231(tt) → U241(tt) at position [] and matcher [ ]

U241(tt)ISLIST
with rule U241(tt) → ISLIST

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.



(73) NO